package demo.practice.linklist;

import demo.practice.Node;


class Dl {
    Node start;
    Node end;

    public Dl(Node start, Node end) {
        this.start = start;
        this.end = end;
    }

}

public class P426 {

    public static void main(String[] args) {
        Node node=new Node(5);
        node.right= new Node(1);

        Node right= new Node(3);
        right.right= new Node(4);
        right.left= new Node(2);

        node.right=right;

        P426 p426= new P426();
        p426.treeToDoublyList(node);
    }


    public Node treeToDoublyList(Node root) {
        if(root==null)
            return null;
        Dl dl = getDl(root);
        dl.start.left = dl.end;
        dl.end.right = dl.start;
        return dl.start;
    }

    public Dl getDl(Node root) {

        if (root == null)
            return null;

        Dl leftDl = null, rightDl = null;
        if (root.left != null) {
            leftDl = getDl(root.left);
        }

        if (root.right != null) {
            rightDl = getDl(root.right);
        }

        if (leftDl != null && leftDl.end != null) {
//            leftDl.end.right = root;
//            root.left = leftDl.end.right;

            root.left=leftDl.end;//当前节点的左子节点为  左边元素集  的尾元素
            leftDl.end.right=root;//
        }


        if (rightDl != null && rightDl.start != null) {
//            rightDl.start.left = root;
//            root.right = rightDl.start.left;
            root.right=rightDl.start;   //当前节点的右子节点为 右边元素集  的头元素
            rightDl.start.left=root;
        }


        return new Dl(leftDl == null || leftDl.start == null ? root : leftDl.start, rightDl == null || rightDl.end == null ? root : rightDl.end);

    }




}
